package com.hr.剑指offer.work1;

import java.util.Stack;

/**
 * @author 周恒哲
 * @date 2020/06/17
 **/
public class 面试题33_二叉搜索树的后序遍历序列 {
    public static boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack=new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length-1; i >=0; i--) {
            if (postorder[i]>root){
                return false;
            }
            while (!stack.isEmpty()&&stack.peek()>postorder[i]){//peek查找最后一个但不删除
                root=stack.pop();//出栈
            }
            stack.push(postorder[i]);//添加
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(面试题33_二叉搜索树的后序遍历序列.verifyPostorder(new int[]{
                1, 3, 2, 6, 5
        }));
    }
}
